package com.future;

/**
 * Description: 583. 两个字符串的删除操作
 *
 * @author weiruibai.vendor
 * Date: 2022/11/10 10:28
 */
public class Solution_583 {
    static Solution_583 instance = new Solution_583();

    public static void main(String[] args) {
        String word1 = "leetcode";
        String word2 = "etco";
        System.out.println(instance.minDistance(word1, word2));
    }

    /**
     * 1、可以先求两个字符串的公共字串的长度（1143. 最长公共子序列）
     * 2、然后把两个字符串的长度分别减去公共串的长度 两个差值的和就是答案
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        /**
         * 1、可以先求两个字符串的公共字串的长度（1143. 最长公共子序列）
         */
        int length = longestCommonStr(word1, word2);
        return (word1.length() + word2.length()) - 2 * length;
    }

    private int longestCommonStr(String word1, String word2) {
        int N = word1.length();
        int M = word2.length();
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int[][] dp = new int[N][M];
        dp[0][0] = chars1[0] == chars2[0] ? 1 : 0;
        for (int j = 1; j < M; j++) {
            dp[0][j] = Math.max(dp[0][j - 1], chars1[0] == chars2[j] ? 1 : 0);
        }
        for (int i = 1; i < N; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], chars1[i] == chars2[0] ? 1 : 0);
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                int val = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (chars1[i] == chars2[j]) {
                    val = Math.max(val, dp[i - 1][j - 1] + 1);
                }
                dp[i][j] = val;
            }
        }
        return dp[N - 1][M - 1];
    }
}
